/**
 * 给你一个字符串s，每一次操作你都可以在字符串的任意位置插入任意字符。
 *
 * 请你返回让s成为回文串的最少操作次数。
 *
 * 「回文串」是正读和反读都相同的字符串。
 *
 * 链接：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome
 */
class MinInsertions {
    /**
     * 法一
     * @param s
     * @return
     */
    public int minInsertionsOne(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=n-1;i>=0;i--) {
            for(int j=i+1;j<n;j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    dp[i][j]=dp[i+1][j-1];
                } else {
                    dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[0][n-1];
    }

    /**
     * 法二
     * @param s
     * @return
     */
    public int minInsertionsTwo(String s) {
        return s.length()-longestPalindromeSubseq(s);//求最长回文子序列然后，那些不在最长回文子序列中的字符不就是需要插入的字符
    }
     public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=0;i<n;i++) {
            dp[i][i]=1;
        }
        for(int i=n-1;i>=0;i--) {
            for(int j=i+1;j<n;j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    dp[i][j]=dp[i+1][j-1]+2;
                } else {
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}